package com.leetcode.根据算法进行分类.滑动窗口相关;

import com.leetcode.根据算法进行分类.单调队列相关.B_剑指Offer59_II_队列的最大值;

import java.util.LinkedList;

/**
 * @author: xiaomi
 * @date: 2021/2/21
 * @description: 1438. 绝对差不超过限制的最长连续子数组
 * https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
 */
public class B_1438_绝对差不超过限制的最长连续子数组 {

    public static void main(String[] args) {
        B_1438_绝对差不超过限制的最长连续子数组 action = new B_1438_绝对差不超过限制的最长连续子数组();
        test2(action);
    }

    public static void test1(B_1438_绝对差不超过限制的最长连续子数组 action) {
        //2
        int[] nums = new int[]{8, 2, 4, 7};
        int limit = 4;
        int res = action.longestSubarray(nums, limit);
        System.out.println("res = " + res);
    }

    public static void test2(B_1438_绝对差不超过限制的最长连续子数组 action) {
        //3
        int[] nums = new int[]{4, 2, 2, 2, 4, 4, 2, 2};
        int limit = 0;
        int res = action.longestSubarray(nums, limit);
        System.out.println("res = " + res);

    }

    /**
     * {@link B_剑指Offer59_II_队列的最大值} 联想到这道题，可以使用双端队列来实现子数组中的 最大/最小值
     * 厉害了我自己！这个答案比标准答案还要快一倍！
     * @param nums
     * @param limit
     * @return
     */
    public int longestSubarray(int[] nums, int limit) {
        //记录最小值的双端队列
        LinkedList<Integer> minDeque = new LinkedList<>();
        //记录最大值的双端队列
        LinkedList<Integer> maxDeque = new LinkedList<>();
        int begin = 0, end = 0;
        int len = nums.length;

        int res = 0;
        while (end < len) {
            //记录最大值队列
            //【注意此处是个循环!因为存在等于的情况！】
//            if (maxDeque.isEmpty()) {
//                maxDeque.addLast(nums[end]);
//            } else {
//                if (maxDeque.peekLast() >= nums[end]) {
//                    maxDeque.addLast(nums[end]);
//                } else {
//                    maxDeque.removeLast();
//                    maxDeque.addLast(nums[end]);
//                }
//            }
            while (!maxDeque.isEmpty() && maxDeque.peekLast() < nums[end]) {
                maxDeque.removeLast();
            }
            maxDeque.addLast(nums[end]);


            //记录最小值队列，minDeque 与 maxDeque 同理
            while (!minDeque.isEmpty() && minDeque.peekLast() > nums[end]) {
                minDeque.removeLast();
            }
            minDeque.addLast(nums[end]);

            if (maxDeque.peekFirst() - minDeque.peekFirst() <= limit) {
                //符合条件
                res = Math.max(res, end - begin + 1);
            } else {
                //开始移动 left 指针

                if (nums[begin] == maxDeque.peekFirst()) {
                    maxDeque.removeFirst();
                }
                if (nums[begin] == minDeque.peekFirst()) {
                    minDeque.removeFirst();
                }
                begin++;
            }
            end++;
        }
        return res;
    }
}
